import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
 * <p>
 * 示例:
 * <p>
 * 输入: [1,2,3]
 * 输出:
 * [
 * [1,2,3],
 * [1,3,2],
 * [2,1,3],
 * [2,3,1],
 * [3,1,2],
 * [3,2,1]
 * ]
 */
class Solution {

    public static void main(String[] args) {
        List<List<Integer>> lists = permute(new int[]{1, 2, 3});
        System.out.println(lists.size());
    }

    public static List<List<Integer>> permute2(int[] nums) {
        return permute2(new ArrayList<List<Integer>>(), nums, nums.length, new boolean[nums.length]);
    }

    public static List<List<Integer>> permute2(List<List<Integer>> all, int[] nums, int length, boolean[] mark) {
        for (int i = 0; i < length; i++) {
            if (!mark[i]) {
                List<Integer> child = new ArrayList<>();
                child.add(nums[i]);
                if (child.size() == length) {
                    all.add(child);
                } else {
                    boolean[] newMark = new boolean[length];
                    // 如果当前mark没有人使用
                    System.arraycopy(mark, 0, newMark, 0, length);
                    newMark[i] = true;
                    permute2(all, child, nums, length, newMark);
                }
            }
        }
        return all;
    }

    public static void permute2(List<List<Integer>> all, List<Integer> child, int[] nums, int length, boolean[] mark) {
        for (int i = 0; i < length; i++) {
            if (!mark[i]) {
                List<Integer> newChild = new ArrayList<>();
                newChild.addAll(child);
                newChild.add(nums[i]);
                if (newChild.size() == length) {
                    all.add(newChild);
                } else {
                    boolean[] newMark = new boolean[length];
                    // 如果当前mark没有人使用
                    System.arraycopy(mark, 0, newMark, 0, length);
                    newMark[i] = true;
                    permute2(all, newChild, nums, length, newMark);
                }
            }
        }
    }

    /**
     * 使用mark记录使用情况
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> all = new ArrayList<List<Integer>>();
        int length = nums.length;
        boolean[] mark = new boolean[nums.length];
        for (int i = 0; i < length; i++) {
            if (!mark[i]) {
                Integer[] child = new Integer[nums.length];
                child[0] = nums[i];
                if (1 == length) {
                    all.add(Arrays.asList(child));
                } else {
                    boolean[] newMark = new boolean[length];
                    // 如果当前mark没有人使用
                    System.arraycopy(mark, 0, newMark, 0, length);
                    newMark[i] = true;
                    permute(all, child, 1, nums, length, newMark);
                }
            }
        }
        return all;
    }


    /**
     * childLen表示当前记录的进度
     *
     * @param all
     * @param child
     * @param childLen
     * @param nums
     * @param length
     * @param mark
     */
    public static void permute(List<List<Integer>> all, Integer[] child, int childLen, int[] nums, int length, boolean[] mark) {
        for (int i = 0; i < length; i++) {
            if (!mark[i]) {
                Integer[] newChild = new Integer[nums.length];
                System.arraycopy(child, 0, newChild, 0, length);
                newChild[childLen] = nums[i];
                ++childLen;
                if (childLen == length) {
                    all.add(Arrays.asList(newChild));
                } else {
                    boolean[] newMark = new boolean[length];
                    // 如果当前mark没有人使用
                    System.arraycopy(mark, 0, newMark, 0, length);
                    newMark[i] = true;
                    permute(all, newChild, childLen, nums, length, newMark);
                    // 回溯进度
                    --childLen;
                }
            }
        }
    }


}
